Subject: Slow E example
From: [email-masked] (Son Huu Le)
To: [email-masked]
Date: Sun, 11 Jul 1993 00:55:07 +1000 (EST)

Forwarded message:
 From MAILER-DAEMON Sat Jul 10 12:16:53 1993
Date: Sat, 10 Jul 93 12:16:30 EST
From: MAILER-DAEMON (Mail Delivery Subsystem)
Subject: Returned mail: Service unavailable
Message-Id: <[email-masked]>
To: s924723

   ----- Transcript of session follows -----
>>> DATA
<<< 554 <[email-masked]>... 550 Host unknown (Authoritative answer from name server)
554 [email-masked]... Service unavailable

   ----- Unsent message follows -----
Received: by minyos.xx.rmit.OZ.AU 
Date: Sat, 10 Jul 93 12:16:30 EST
From: s924723 (Son Huu Le)
Message-Id: <[email-masked]>
To: [email-masked]
Subject: Slow_E

Okay. Here's the slow E port of boyerm.c - It's been stripped of the
non-essential routines and has a few features hard-coded (laziness, I know :)
Basically it searches my Aminet catalogue for Toolmanager2.0 (there's only
one entry) using Boyer-Moore string search. I compiled practically the same
code in C format (of coz) using SAS/C v6.3 and the results were something
like 30secs for SAS/C and 60 secs for E.

Any help much appreciated.

Son Le

PS. Another idea would be to include a set of standard functions with E for
basic functions like atoi, islower, etc. And also about the .o files, how
about mimicking c.o with e.o?

/* boyerm - find lines containing given constant string       */
/* A. Kotanski, 1989                                          */
/* For explanation of the method see the following articles : */
/* R.S.Boyer, J.S. Moore, "A fast string search algorithm"    */
/*                        Comm. ACM 20, 762-772 (1977)        */
/* D.E.Knuth, J.H.Morris and V.B.Pratt                        */
/*                        "Fast pattern matching in strings"  */
/*                        SIAM J. Computing, 6, 323-350 (1977)*/

CONST UPPER=255

DEF except = 0, number = 0, ppos = 1, patlen, stringlen, c,
    delta0[128]:STRING, delta2[80]:STRING, string[256]:STRING,
    pat[80]:STRING, f[80]:STRING

PROC max(a,b) RETURN (IF a>b THEN a ELSE b)
PROC min(a,b) RETURN (IF a>b THEN b ELSE a)

PROC boyer()
DEF i, j

   IF ( (i := patlen + ppos - 2) >= stringlen ) THEN RETURN 0
   LOOP
      WHILE ( (i := i + delta0[string[i]]) < stringlen ) DO NOP
      IF ( i < UPPER ) THEN RETURN 0
      i := i - (UPPER + 1)
      IF ( (j := patlen - 2) < 0 ) THEN RETURN (i + 2)
      WHILE ( string[i] = pat[j] )
         i--
         IF ( j-- < 0 ) THEN RETURN (i + 2)
      ENDWHILE
      IF ( string[i] = pat[patlen-1] )
         i := i + delta2[j]
      ELSE
         i := i + max(delta0[string[i]], delta2[j])
      ENDIF
      IF CtrlC()=TRUE THEN Raise(0)
   ENDLOOP
ENDPROC

PROC main() HANDLE  /* find pattern from first argument */
DEF lineno = 0, match, i, t, fh

   IF (fh := Open (arg,OLDFILE))=NIL
      WriteF('Open error\n')
      CleanUp(0)
   ENDIF
   StrCopy(pat,'ToolManager2.0',ALL)

   patlen := StrLen(pat)

   FOR i := 0 TO 127 DO delta0[i] := patlen
   FOR i := 0 TO patlen-1 DO delta0[pat[i]] := patlen - i - 1

   delta0[pat[patlen - 1]] := UPPER

   FOR i := 0 TO patlen-1 DO delta2[i] := patlen + patlen - i - 1

   i := patlen - 1
   t := patlen
   WHILE ( i >= 0 )
      f[i] := t
      WHILE ( ( t < patlen ) AND ( pat[i] <> pat[t] ) ) 
         delta2[t] := min(delta2[t], patlen-i-1)
         t := f[t]
      ENDWHILE
      t--
      i--
   ENDWHILE
   FOR i := 0 TO t DO delta2[i] := min(delta2[i], patlen + t - i)

   WHILE Fgets(fh, string, 256)
      lineno++
      stringlen := StrLen(string)
      match := boyer()
      IF match THEN WriteF('\s',string)
   ENDWHILE
   Raise(0)
EXCEPT
   IF fh THEN Close(fh)
ENDPROC